| Senden Sie eine E-Mail an
| creator |
Lohrey, Markus
| | date |
2005-01-05
| | | | description |
41 pages
| |
Hierarchical graph definitions allow a modular description of graphs
using modules for the specification of repeated substructures.
Beside this modularity, hierarchical graph definitions also allow to
specify graphs of exponential size using polynomial size
descriptions. In many cases, this succinctness increases the
computational complexity of decision problems when input graphs are
defined hierarchical. In this paper, the model-checking problem for
first-order logic (FO), monadic second-order logic (MSO), and
second-order logic (SO) on hierarchically defined input graphs is
investigated. It is shown that in general these model-checking
problems are exponentially harder than their non-hierarchical
counterparts, where the input graphs are given explicitly. As a
consequence, several new complete problems for the levels of the
polynomial time hierarchy and the exponential time hierarchy are
obtained. Based on classical results of Gaifman and Courcelle, two
restrictions on the structure of hierarchical graph definitions that
lead to more efficient model-checking algorithms are presented.
| | format |
application/pdf
| | 353656 Bytes | |